1. Field of the Invention
The invention generally relates to combining or fusing data from sensors. In particular, the invention relates to robust techniques for a robot of combining data that may include potentially unreliable data.
2. Description of Related Art
The problem of estimating a characteristic that cannot be known with certainty is common. For example, if sensor measurements with known statistical properties and correlated with the characteristic are available, i.e., the measurements are noisy or incomplete, and the measurements are acquired over time, then the optimal and consistent way to solve the above problem is known as probabilistic inference or sequential probabilistic inference.
In a Bayesian framework, one can express an optimal filtering method that accounts for any nonlinearity and any statistical distribution. Although such a method provides an optimal recursive solution, it can generally be reduced to a closed form only for linear Gaussian systems, whereas for most real-world systems (nonlinear and/or non-Gaussian), approximate solutions will typically be used.
A flexible approximation of the solution is obtained by implementing the filtering method using a sequential Monte-Carlo method, such as, for example, a particle filter. The idea behind the Monte-Carlo methods, and, in particular, the particle filter, is to approximate the relevant statistical distributions by a finite number of samples, also called particles, and to update the distributions as observations are received by appropriately generating new random samples. By using a particle filter, complex nonlinear computations can often be avoided.
However, a disadvantage of the standard particle filter is that it often fails to update the estimate of characteristic correctly, and, often, if the error in the initial estimate is large, the estimate converges relatively slowly, or not at all. This weakness is due to the limited number of samples used to approximate the relevant probability distributions; namely, the samples tend to cluster more than is appropriate in regions where the density function is relatively large. Hence, the probability of an unknown characteristic to be a value in an unlikely region is usually too small to be represented by a discrete sample and is often estimated to be zero. A conventional technique to reduce this limitation is to use a relatively large number of samples (particles), which disadvantageously results in a large computational requirement on the filtering process. In addition, the statistical properties of the measurements are typically not known with accuracy, which can cause the performance of particle filter to break down.
One example in which the above scenario exists is in the autonomous localization of mobile robots. In particular, if a robot is lifted and moved to a new location without receiving an indication that such motion has occurred, it has been exposed to what is called “kidnapping.” The unknown characteristic (the characteristic to be estimated) is the pose (location and orientation) of the robot, while the observations on which the estimation is based, include dead reckoning measurements, such as wheel odometry, and observations from one or more sensors that give global measurements rather than incremental measurements, such as images from a camera, scans from a laser range finder, measurements from SONAR, IR, and LIDAR sensors, and the like. If relatively many observations have been made and processed before kidnapping occurs and an appropriate algorithm for the sensor fusion is used, then the estimate of the unknown characteristic (the robot pose) will typically have converged, and the confidence of the estimate will typically be relatively high. However, immediately after the kidnapping, this estimate is very likely to be wrong because that most conventional methods of data fusion are not able to recover the pose in a short amount of time.
The above scenario demonstrates that a more robust treatment of observations and estimated distributions is valuable for a successful implementation of Monte-Carlo methods, such as the particle filter, to allow for faster and more reliable recovery from kidnapping.
Monte Carlo techniques are sometimes used for implementing various probabilistic methods in robotics.
Dieter Fox, Sebastian Thrun, Wolfram Burgard, and Frank Dellaert, Particle filters for mobile robot localization, Sequential Monte Carlo Methods in Practice, (Doucet, A., de Freitas, N., and Gordon, N., eds.) Springer Verlag, pp. 401-428, 2001, and Sebastian Thrun, Mapping: A Survey, Technical Report, CMU-CS-02-111, Carnegie Mellon University, Pittsburgh, Pa., February 2002 describe uses of particle filtering in the field of mobile robot navigation. These references show that the use of particle filters enables a solution to certain previously unsolved problems. One example of such a problem is known as global localization. Another example of such a problem is known as the kidnapped robot problem, in which the robot is lifted and moved to a new location without receiving an indication that such motion has occurred. One important difference between global localization and recovery from kidnapping is that in a kidnapping scenario, the robot “thinks” it knows where it is (i.e., it has some pre-existing estimate of its pose) at the same time as it is lost, while in the global localization scenario, the robot knows that it is completely lost (i.e., it has no pre-existing estimate of its pose).
Methods have been proposed to solve the problem of simultaneous localization and mapping (SLAM) (see Michael Montemerlo, Sebastian Thrun, Daphne Keller, and Ben Wegbreig, FastSLAM: A factored solution to the simultaneous localization and mapping problem, in Proceedings of the AAAI National Conference on Artificial Intelligence, Edmonton, Canada, 2002). An important weakness of the methods described in Montemerlo, et al., id. is that if the robot is kidnapped a relatively short time before the map is expanded (i.e., a new feature, such as a new landmark, is added to the map), then it will be relatively difficult for the robot to recover and fully correct the map. A second disadvantage of the methods described in reference 4 lies in the so-called “landmarks” that form the basis for its map. These landmarks are based on laser range scans, and it becomes crucial to associate the data acquired during a new laser scan with the data acquired during a previously acquired laser scan correctly. “vSLAM”, however, addresses these two weaknesses by introducing two kind of particles, termed “primary” and “dual” particles (see also Fox, Thrun, Burgard, and Dellaert, id., and A. C. Davison and D. V. Hinkley, Bootstrap Methods and Their Application, Cambridge Series in Statistical and Probabilistic Methods, Cambridge, United Kingdom, pp. 450-466, 1997). Additionally, the data association problem is resolved by using relatively more robust visual landmarks, wherein false association of an acquired image with a previously acquired image is relatively rare.